package LC;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author lhn
 * @date 2024-09-25 11:24
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap3(height1));  // Output: 6

//        int[] height2 = {4, 2, 0, 3, 2, 5};
//        System.out.println(trap2(height2));  // Output: 9
    }

    public static int trap(int[] height) {
        int len = height.length;
        if (len < 3) return 0;
        int sum = 0;
        int[] left = new int[len];  // 记录每个位置左边最高的高度
        int[] right = new int[len]; // 记录每个位置右边最高的高度
        for (int i = 0; i < len; i++) {
            if (i == 0) left[i] = 0;
            else left[i] = Math.max(left[i - 1], height[i - 1]);    // 更新左边最高高度
        }
        for (int i = len - 1; i >= 0; i--) {
            if (i == len - 1) right[i] = 0;
            else right[i] = Math.max(right[i + 1], height[i + 1]);  // 更新右边最高高度
        }
        //  取交集
        for (int i = 0; i < len; i++) {
            int cur = Math.min(left[i], right[i]) - height[i];// 找到当前位置的最小高度，减去当前高度，得到当前位置能接的雨水数目
            sum = sum + Math.max(cur, 0);   // 可能出现当前的 cur < 0
//            System.out.println("i = " + i + " sum = " + sum);
        }
        return sum;
    }

    //
    public static int trap2(int[] height) {
        int sum = 0;
        Deque<Integer> stack = new LinkedList<Integer>();   // 栈存放下标
        int len = height.length;
        for (int i = 0; i < len; i++) {
            // 栈不为空 和 当前位置高度大于栈顶位置高度
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();  // 出栈
                if (stack.isEmpty()) break; // 判断stack中是否只存在一个元素（是否为左边界）
                int left = stack.peek();    // 返回栈顶位置
                int curWidth = i - left - 1;
                int curHeight = Math.min(height[left], height[i]) - height[top];
                sum = sum + curWidth * curHeight;
            }
            stack.push(i);  // 入栈
        }
        return sum;
    }

    // 双指针
    //左右指针从两端向中间移动，想要正确计算储水量需要知道本端的最高点高度，
    // 以及确保对方有一个不低于本端最高点的柱子。 左右两端轮流占领目前遍历到
    // 的最高点，当一方占据着全局最高点时。另一方前进，直到遇到了一个比全局最
    // 高点更高的点，换另一方前进，循环往复直到 left, right 碰面。可移动的
    // 一方每步更新自己这侧的最高点，由于另一方此时占据着全局最高点，所以可以
    // 保证另一方有一个不低于本方最高点的柱子，也就确保了当前对储水量的计算是正确的
    public static int trap3(int[] height) {
        int len = height.length;
        if (len < 3) return 0;
        int sum = 0;
        int left = 0;
        int right = len - 1;
        int leftMax = 0;
        int rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                sum = sum + leftMax - height[left];
                left ++;
            } else {
                sum = sum + rightMax - height[right];
                right --;
            }
        }
        return sum;
    }
}
